package com.learn._5tree;

/**
 * 递归和循环两种方式都实现
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] input = {3,6,9,11,13,31};

        System.out.println(binarySearch(input,15));
    }


    //TODO 递归和循环的关系，    递归和循环的转换技巧

    //这里的递归是单链的，即上次调用后，紧接下来只会产生一次调用，因此调用链只有一条，对于这种调用链只有一条的递归，是非常容易转换成循环的,只要把每次递归的输入
    //参数作为循环的全局循环参数即可，由于只有一条调用链，其输出的下一批参数和本批参数的转换关系和数量是确定的，而一个循环可以完成对参数的固定转换，因此可以实现单链。
    //
    // 而多链（每个递归函数递归调用多次自己的函数），在每次调用里，其输出的下一批参数与本批参数的转换关系 是存在多种的，因此无法用一个循环来完成逻辑，常常需要利用
    //回溯的方法来实现递归转循环，而实际上，递归本身也是一个回溯。
    private static int binarySearch(int[] input,int target){
        return binarySearchInner(input,0,input.length - 1,target);
    }

    private static int binarySearchInner(int[] input, int start, int end, int target) {

        if(start > end){
            return -1;
        }
        if(start == end){
            return input[start] == target?start: -1;
        }

        int middle = (start + end)/2;
        if(target > input[middle]){
            return binarySearchInner(input,middle + 1,end,target);
        }else if(target < input[middle]){
            return binarySearchInner(input,start,middle - 1,target);
        }else{
            return middle;
        }
    }


}
